An optimization algorithm may be used to determine a solution for a problem in which the solution considers all variables and constraints related to the problem and provides a lowest cost configuration of the values for all the variables. For example, in a televised event, a plurality of cameras may be used to capture the event. The cameras may move along planned trajectories to fully capture the event. Accordingly, the problem associated with such a scenario may be to determine the planned trajectories for the cameras that incorporate the variables and constraints associated therewith. Such variables and constraints may include no overlap of space as the cameras cannot physically be co-located at a common time, a trajectory path that provides a sufficient video capture of the event, a tracking algorithm for the occurrences during the event, etc. Through incorporation of all these considerations, the optimization algorithm may determine the trajectories of the cameras to provide the lowest cost solution (e.g., least distance to be covered by the cameras, best coverage of the event, least energy requirements, etc.). However, most optimization algorithms require significantly high processing requirements for all these considerations to be assessed as well as provide the lowest cost solution to the problem.
A conventional algorithm used for convex optimization is the Alternating Direction Method of Multipliers (ADMM). Conventionally, the ADMM algorithm is a variant of an augmented Lagrangian scheme that uses partial updates for dual variables. This algorithm has also been utilized and shown to be well-suited for distributed implementations. Further developments in using the ADMM algorithm have included being used in applications such as Linear Programming (LP) decoding of error-correcting codes and compressed sensing.
However, the ADMM algorithm has in practice been used exclusively for convex optimization problems. Convex optimization problems have a special form for the cost objective function, and in particular, only one local optimum exists for a given problem (e.g., a landscape including one valley has a single solution as to what is the lowest point). Many optimization problems of interest, such as the problem of finding optimal trajectories introduced earlier, are not convex. The basic principles behind the ADMM algorithm including the convexity assumptions underlying the derivation of ADMM, appear to provide a gross contradiction to its application to non-convex problems. That is, conventional uses of the ADMM algorithm are not designed for use with general optimization functions. In particular, the ADMM algorithm was not designed as a heuristic optimization algorithm for non-convex Non-Deterministic Polynomial-Time (NP) hard optimization problems. In such problems, multiple local optima exist for a given problem (e.g., a landscape including various hills and valleys has more than one solution as to what is the lowest point as well as the highest point).
Another conventional approach for optimization uses graphical models in which a graph denotes conditional dependencies between random variables. The graphical models often are combined with a Belief Propagation (BP) message-passing algorithm in which inferences are performed on the graphical models. The BP message-passing algorithm calculates the marginal distribution for each unobserved node, conditional on any observed nodes within the graphical model.